package com.itheima.array;

public class QuitSort {
    public static void main(String[] args) {
//        1，从右开始找比基准数小的
//        2，从左开始找比基准数大的
//        3，交换两个值的位置
//        4，红色继续往左找，蓝色继续往右找，直到两个箭头指向同一个索引为止
//        5，基准数归位
        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};

        quiteSort(arr,0,arr.length-1);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    private static void quiteSort(int[] arr, int begin, int end) {
        if(end<begin){
            return;
        }
        int yuanshi =begin;
        int yuanshiYou=end;
        int shu=arr[yuanshi];
        while(begin!=end){
            while(arr[end]>=shu&&begin<end){
                end--;
            }
            while (arr[begin]<=shu&&begin<end){
                begin++;
            }
            int temp= arr[begin];
            arr[begin]=arr[end];
            arr[end]=temp;
        }
        int temp= arr[begin];
        arr[begin]=shu;
        arr[yuanshi]=temp;
        quiteSort(arr,yuanshi,begin-1);
        quiteSort(arr,begin+1,yuanshiYou);

    }
}
